#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
int n,m,k,a[MAXN],c[MAXN],nxt[MAXN],fst[MAXN],l;
struct node
{
	int l,r,num,ans;
}q[MAXN];
bool cmp1(node a,node b)
{
	return a.l==b.l?a.r<b.r:a.l<b.l;
}
bool cmp2(node a,node b)
{
	return a.num<b.num;
}
int lowbit(int x)
{
	return x&-x;
}
void update(int o,int x)
{
	while(o<=n)
	{
		c[o]+=x;
		o+=lowbit(o);
	}
	return;
}
int query(int o)
{
	int ans=0;
	while(o)
	{
		ans+=c[o];
		o-=lowbit(o);
	}
	return ans;
}
int main()
{
	scanf("%d%d%d",&n,&k,&m);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	for(int i=n;i;--i)
	{
		nxt[i]=fst[a[i]];
		fst[a[i]]=i;
	}
	for(int i=1;i<=k;++i)
		if(nxt[fst[i]])update(nxt[fst[i]],1);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].num=i;
	}
	sort(q+1,q+1+m,cmp1);
	for(int i=1;i<=m;++i)
	{
		while(l<q[i].l-1)
		{
			if(nxt[++l])update(nxt[l],-1);
			if(nxt[nxt[l]])update(nxt[nxt[l]],1);
		}
		q[i].ans=query(q[i].r)-query(q[i].l-1);
	}
	sort(q+1,q+1+m,cmp2);
	for(int i=1;i<=m;++i)printf("%d\n",q[i].ans);
	return 0;
}
